package main

import "fmt"

//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//
//示例 1：
//
//输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
//示例 2：
//
//输入: "cbbd"
//输出: "bb"

//回文子串
func huiwen(str string) string{
	nLen := len(str)
	dp := make([][]bool, nLen)
	for i := 0; i < nLen; i++{
		dp[i] = make([]bool, nLen)
	}

	l, r := 0, 0
	for i := nLen-1; i >= 0; i--{
		dp[i][i] = true
		for j := i+1; j < nLen; j++{
			dp[i][j] = str[i] == str[j] && dp[i+1][j-1]
			if dp[i][j] {
				r = j
				l = i
			}
		}
	}
	return str[l:r+1]
}

func main(){
	fmt.Println(huiwen("ada"))
}